#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void swap(int* as, int* aq)
{
	int tmp = *as;
	*as = *aq;
	*aq = tmp;
}
int sanshuquzhong(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] > a[right])
	{
		if (a[mid] > a[left])
		{
			return left;
		}
		else if (a[mid] > a[right])
		{
			return mid;
		}
		else
		{
			return right;
		}
	}
	else
	{
		if (a[mid] > a[right])
		{
			return right;
		}
		else if (a[mid] > a[left])
		{
			return mid;
		}
		else
		{
			return left;
		}
	}
}
void charu(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}
void kuaisupaixu(int* a, int left,int right)
{
	if (left >= right)
	{
		return 0;
	}
	if (right + left - 1 < 10)
	{
		charu(a + left, right + left - 1);
	}
	int mid = sanshuquzhong(a, left, right);
	swap(&a[mid], &a[left]);
	int key = left;
	int drev = left;
	int cur = drev + 1;
	while (cur <= right)
	{
		if (a[cur] < a[key] && ++drev != cur)
		{
			swap(&a[drev], &a[cur]);
		}
		cur++;
	}
	swap(&a[drev], &a[key]);
	key = drev;
	kuaisupaixu(a, left, key - 1);
	kuaisupaixu(a, key+1,right);
}
int main()
{
	int arr[] = { 2345,6354,5476,356877,6584,76,8798,95,790,9870,8579,8579,87,2,72,658,67598,371234,543,4624,57,4257,657,653,877365,876,988,79,5789,5780,57809,8,9 };
	kuaisupaixu(arr,0, sizeof(arr) / sizeof(arr[0])-1);
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		printf("%d ", arr[i]);


	}
	return 0;
}